#pragma once
#include <iostream>
using namespace std;
namespace K
{
	template <class K>
	struct BSTreeNode
	{
		BSTreeNode<K>* _left;
		BSTreeNode<K>* _right;
		K _key;

		BSTreeNode(const K& key)
			:_left(nullptr)
			,_right(nullptr)
			,_key(key)
		{}
	};

	template <class K>
	class BSTree
	{
		typedef BSTreeNode<K> Node;
	public:
		bool Insert(const K& key)
		{
			if (_root == nullptr) {
				_root = new Node(key);
				return true;
			}
			Node* cur = _root;
			Node* parent = nullptr;
			while (cur) {
				if (cur->_key < key) {
					parent = cur;
					cur = cur->_right;
				}
				else if (cur->_key > key) {
					parent = cur;
					cur = cur->_left;
				}
				else {
					return false;
				}
			}

				cur = new Node(key);
				if (parent->_key < key) {
					parent->_right = cur;
				}
				else {
					parent->_left = cur;
				}
				return true;
		}
		void InOrder() {
			_InOrder(_root);
			cout << endl;
		}
		bool Find(const K& key)
		{
			Node* cur = _root;
			while (cur) {
				if (cur->_key < key) {
					cur = cur->_right;
				}
				else if (cur->_key > key) {
					cur = cur->_left;
				}
				else
				{
					return true;
				}
			}
			return false;
		}

	private:
		void _InOrder(Node* root) {
			if (root == nullptr) {
				return;
			}
			_InOrder(root->_left);
			cout << root->_key << " ";
			_InOrder(root->_right);
		}

	private:
		Node* _root = nullptr;
	};

	void BSTreeTest1()
	{
		BSTree<int> bst;
		int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
		for (auto e : a) {
			bst.Insert(e);
		}
		/*bst.Insert(5);
		bst.Insert(4);
		bst.Insert(7);
		bst.Insert(6);
		bst.Insert(3);*/
		bst.InOrder();
		cout << bst.Find(3) << endl;
		cout << bst.Find(14) << endl;
		cout << bst.Find(13) << endl;
		cout << bst.Find(0) << endl;
	}
}